<#390#>Appendix A Estimating Pythagorean Square-root<#390#>
For the line drawing commands described in the main sections of this
document, we need to estimate the Pythagorean square-root in order to
determine the length of the line (along its slope). More precisely, we need
to estimate the number of segments of a given length needed to draw a line.
TEX does not provide for floating point calculations, and thus there are no
direct means of calculating the above square-root. Most standard numerical
techniques are iterative and would be too slow when used with TEX for lack
of floating point calculations, and in particular, real division, since
calculation of such a square-root is needed very frequently.
A simple non-iterative formula for estimating the square-root is derived and described below.
<#391#>Problem: <#391#> Given a and b, to find c =
We can get very tight bounds on the square-root as follows. Without loss of generality, let a≥b. We seek a simple n such that:
Squaring both sides, we have
⇔ | a2 + b2 | ≥ | a2 + |
⇔ | (1 - |
≥ | |
⇔ | ≥ | ||
<#1#>or <#1#> | ( |
≥ | 0 |
From the quadratic equation above, we finally get an expression for n,
Only the +ve root interests us since n has to be positive.
Note that the term under the root is bounded above and below (since
Hence, we have two values for n,
These are very tight bounds. Denoting the lower bound as cl and upper one cu, below are some numerical results (c = exact square-root):
a | b | c | cl | cu |
100.0 | 100.0 | 141.4213 | 141.4213 | 150.0 |
100.0 | ;SPMnbsp;80.0 | 128.0642 | 126.5096 | 132.0 |
;SPMnbsp;30.0 | ;SPMnbsp;20.0 | ;SPMnbsp;36.0555 | 35.5228 | 36.6667 |
With the above bounds, one can do a linear interpolation to get exact values. In our case, since it is not required to be <#448#>extremely<#448#> accurate, for estimating the square-root in the line drawing commands, we simply take the midpoint of the two bounds. For small numbers, which is expected to be the case most of the time, the error is very small.
With some algebra, we get the mid-point estimate of c,
The macro
Note that since divisions in TEX are integer-divisions, it is simpler to
deal in ``number of segments'' rather than actual lengths
(e.g. in the expression above,
<#465#>Caveat:<#465#> The approach presented here for estimation of Pythagorean square-root is an independent effort by the author. It may already exist in the literature --- the author is neither aware of it nor has he made any serious attempts at uncovering it.